package suanfa;

/**
 * Description:
 * Author:    Dane
 * CreateTime:2024/10/9-上午10:00
 * Since  :   1.0
 * Version:   1.0
 */
public class DP {

//    public static boolean canPartition(int[] nums) {
//        int count = 0;
//        for (int i : nums) {
//            count +=i;
//        }
//
//        if (count % 2 != 0) {
//            return false;
//        }
//        int target = count / 2;
//        int[] dp = new int[target + 1];
//        for (int i = 0; i < nums.length; i++) {
//            for (int j = target; j >= nums[i]; j--) {
//                if (j - nums[i] >= 0) {
//                    dp[j] = Math.max(dp[j], nums[i] + dp[j - nums[i]]);
//                }
//            }
//        }
//
//
//        return dp[target]==target;
//    }

    public static boolean canPartition(int[] nums) {
        int count = 0;
        for (int i : nums) {
            count += i;
        }
        if (count % 2 != 0) {
            return false;
        }
        int target = count / 2;
        int[] dp = new int[target + 1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = target; target >= nums[i]; target--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[target] == target;


    }

    public int lastStoneWeightII(int[] stones) {
//      int count=0;
//      for (int i:stones){
//          count+=i;
//      }
//      int target=count/2;
//      int dp[]=new int [target+1];
//        for (int i = 0; i < stones.length; i++) {
//            for (int j = target; j >=stones[i] ; j--) {
//                if (j-stones[i]>=0){
//                    dp[j]=Math.max(dp[j],stones[i]+dp[j-stones[i]]);
//                }
//            }
//
//        }
//        return count-2*dp[target];
        int count = 0;
        for (int i : stones) {
            count += i;
        }
        int target = count / 2;
        int[] dp = new int[target + 1];
        for (int i = 0; i < stones.length; i++) {
            for (int j = target; j >= stones[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }

        }
        return count - 2 * dp[target];


    }

    public static int findTargetSumWays(int[] nums, int target) {
        int count = 0;
        for (int i : nums) {
            count += i;
        }
        if ((count + target) % 2 != 0) {
            return 0;
        }
        int left = (count + target) / 2;
        int[] dp = new int[left + 1];
        dp[0] = 1;


        for (int i = 0; i < nums.length; i++) {
            for (int j = left; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];

            }

        }
        return dp[target];

    }

    public static void main(String[] args) {
//        int nums[] = {1, 5, 11, 5};
//        canPartition(nums);
        int nums[] = {1, 1, 1, 1, 1};
        int target=3;
        findTargetSumWays(nums,target);

    }

}
